{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #三数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: threeSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #三数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含 <code>n</code> 个整数的数组&nbsp;<code>nums</code>，判断&nbsp;<code>nums</code>&nbsp;中是否存在三个元素&nbsp;<code>a</code> ，<code>b</code> ，<code>c</code> <em>，</em>使得&nbsp;<code>a + b + c = 0</code> ？请找出所有和为 <code>0</code> 且&nbsp;<strong>不重复&nbsp;</strong>的三元组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-1,0,1,2,-1,-4]\n",
    "<strong>输出：</strong>[[-1,-1,2],[-1,0,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0]\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= nums.length &lt;= 3000</code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 15&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/3sum/\">https://leetcode-cn.com/problems/3sum/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [1fGaJU](https://leetcode.cn/problems/1fGaJU/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [1fGaJU](https://leetcode.cn/problems/1fGaJU/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,0,1,2,-1,-4]', '[]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        ans=set()\n",
    "        length =len(nums)\n",
    "        if(length<3):return []\n",
    "        for i in range(length-2):\n",
    "            target=-nums[i]\n",
    "            j=i+1\n",
    "            k=length-1\n",
    "            while(j<k):\n",
    "                total=nums[j]+nums[k]\n",
    "                if(total<target):\n",
    "                    j+=1\n",
    "                elif(total>target):\n",
    "                    k-=1\n",
    "                else:\n",
    "                    ans.add((nums[i],nums[j],nums[k]))\n",
    "                    j+=1\n",
    "                    # break\n",
    "        # [0,0,0,0] 重复错误,下进行重复检查 set去重\n",
    "        # print(ans)\n",
    "        answer=list(ans)\n",
    "        # print(answer)\n",
    "        return answer\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        m = len(nums)\n",
    "        for first in range(m - 2):\n",
    "            if first > 0 and nums[first] == nums[first - 1]: continue\n",
    "            target = -nums[first]\n",
    "            second = first + 1\n",
    "            third = m - 1\n",
    "            while second < third:\n",
    "                if second > first + 1 and nums[second] == nums[second - 1]: \n",
    "                    second += 1\n",
    "                    continue\n",
    "                if third < m - 1 and nums[third] == nums[third + 1]: \n",
    "                    third -= 1\n",
    "                    continue\n",
    "                if nums[second] + nums[third] == target:\n",
    "                    ans.append([nums[first], nums[second], nums[third]])\n",
    "                    second += 1\n",
    "                elif nums[second] + nums[third] > target:\n",
    "                    third -= 1\n",
    "                else:\n",
    "                    second += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        #1e3 1e6<1e8\n",
    "        #这里我的算法还是走进去了，其实可以判定直接跳过\n",
    "\n",
    "\n",
    "        result=[]\n",
    "        r=set()\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            start=i+1\n",
    "            end=len(nums)-1\n",
    "            if i>0 and nums[i]==nums[i-1]:\n",
    "                continue\n",
    "            for j in range(start,end):\n",
    "                if j>start and nums[j]==nums[j-1]:\n",
    "                    continue\n",
    "                while j<end and nums[i]+nums[j]+nums[end]>0:\n",
    "                    end-=1\n",
    "                if j==end:\n",
    "                    break\n",
    "                if nums[i]+nums[j]+nums[end]==0:\n",
    "                    result.append((nums[i],nums[j],nums[end]))\n",
    "        return result\n",
    "             \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        group = set()\n",
    "        for i in range(len(nums)-2):\n",
    "            j,k = i+1, len(nums) -1\n",
    "            while j < k:\n",
    "                if nums[i] + nums[j] + nums[k] == 0:\n",
    "                    group.add((nums[i], nums[j], nums[k]))\n",
    "                    j += 1\n",
    "                elif  nums[i] + nums[j] + nums[k] > 0:\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    j += 1 \n",
    "        return list(group)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        if not nums or len(nums) < 3:\n",
    "            return []\n",
    "        ans = set([])\n",
    "        for i in range(len(nums)):\n",
    "            l = i + 1\n",
    "            r = len(nums) - 1 \n",
    "            while l < r:\n",
    "                if nums[l] + nums[r] + nums[i] < 0:\n",
    "                    l+=1\n",
    "                elif nums[l] + nums[r] + nums[i] > 0:\n",
    "                    r-=1\n",
    "                else: \n",
    "                    ans.add((nums[l] , nums[r] , nums[i]))\n",
    "                    l+=1\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums)<3:\n",
    "            return []\n",
    "        nums.sort()#\n",
    "        target=0\n",
    "        ans =set()\n",
    "        for i in range(len(nums)-2):\n",
    "                now = nums[i]\n",
    "                p=i+1\n",
    "                q=len(nums)-1\n",
    "                while p<q:\n",
    "                    if now+nums[p]+nums[q]==target:\n",
    "                        if (nums[i],nums[p],nums[q]) not in ans:\n",
    "                            ans.add((nums[i],nums[p],nums[q]))\n",
    "                    if now+nums[p]+nums[q] > target:\n",
    "                        q-=1\n",
    "                    else:\n",
    "                        p+=1\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = set()\n",
    "        for i in range(len(nums)):\n",
    "            l = i-1\n",
    "            r = i+1\n",
    "            while l >= 0 and r < len(nums):\n",
    "                s = nums[l] + nums[i] + nums[r]\n",
    "                tmpl = nums[l]\n",
    "                tmpr = nums[r]\n",
    "                if s == 0:\n",
    "\n",
    "                    res.add((nums[l], nums[i], nums[r]))\n",
    "                    r += 1\n",
    "                    l -= 1\n",
    "                elif s < 0:\n",
    "                    r += 1\n",
    "                else:\n",
    "                    l -= 1\n",
    "        return list(res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        if not nums or len(nums) < 3:\n",
    "            return []\n",
    "        ans = set([])\n",
    "        for i in range(len(nums)):\n",
    "            l = i + 1\n",
    "            r = len(nums) - 1 \n",
    "            while l < r:\n",
    "                if nums[l] + nums[r] + nums[i] < 0:\n",
    "                    l+=1\n",
    "                elif nums[l] + nums[r] + nums[i] > 0:\n",
    "                    r-=1\n",
    "                else: \n",
    "                    ans.add((nums[l] , nums[r] , nums[i]))\n",
    "                    l+=1\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums = sorted(nums)\n",
    "        ans = set()\n",
    "        for i in range(len(nums)-2):\n",
    "            l, r = i+1, len(nums)-1\n",
    "            while l < r:\n",
    "                if nums[i]+nums[l]+nums[r] == 0:\n",
    "                    ans.add((nums[i], nums[l], nums[r]))\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                elif nums[i]+nums[l]+nums[r] < 0:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "        return list(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "\n",
    "        for a in range(len(nums)-2):\n",
    "            if a > 0 and nums[a] == nums[a-1]:\n",
    "                continue\n",
    "\n",
    "            c = len(nums) - 1\n",
    "            for b in range(a+1, len(nums)-1):\n",
    "                if b > a+1 and nums[b] == nums[b-1]:\n",
    "                    continue\n",
    "                if nums[a] + nums[b] + nums[c] < 0:\n",
    "                    continue\n",
    "                while b < c and nums[a] + nums[b] + nums[c] > 0:\n",
    "                    c -= 1\n",
    "                if b == c:\n",
    "                    break\n",
    "                if b < c and nums[a] + nums[b] + nums[c] == 0:\n",
    "                    res.append((nums[a], nums[b], nums[c]))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "\n",
    "        for a in range(len(nums)-2):\n",
    "            if a > 0 and nums[a] == nums[a-1]:\n",
    "                continue\n",
    "\n",
    "            c = len(nums) - 1\n",
    "            for b in range(a+1, len(nums)-1):\n",
    "                if b > a+1 and nums[b] == nums[b-1]:\n",
    "                    continue\n",
    "\n",
    "                while b < c and nums[a] + nums[b] + nums[c] > 0:\n",
    "                    c -= 1\n",
    "                if b == c:\n",
    "                    break\n",
    "                if nums[a] + nums[b] + nums[c] == 0:\n",
    "                    res.append((nums[a], nums[b], nums[c]))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = set()\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return []\n",
    "        \n",
    "        nums.sort()\n",
    "        for i in range(n-2):\n",
    "            left, right = i + 1, n - 1\n",
    "            while left < right:\n",
    "                if nums[i] + nums[left] + nums[right] == 0:\n",
    "                    res.add((nums[i], nums[left], nums[right]))\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                elif nums[i] + nums[left] + nums[right] < 0:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "\n",
    "        for a in range(len(nums)-2):\n",
    "            if a > 0 and nums[a] == nums[a-1]:\n",
    "                continue\n",
    "\n",
    "            c = len(nums) - 1\n",
    "            for b in range(a+1, len(nums)-1):\n",
    "                if b >= c:\n",
    "                    break\n",
    "                if b > a+1 and nums[b] == nums[b-1]:\n",
    "                    continue\n",
    "                if nums[a] + nums[b] + nums[c] < 0:\n",
    "                    continue\n",
    "                while b < c and nums[a] + nums[b] + nums[c] > 0:\n",
    "                    c -= 1\n",
    "                if b < c and nums[a] + nums[b] + nums[c] == 0:\n",
    "                    res.append((nums[a], nums[b], nums[c]))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "\n",
    "        for a in range(len(nums)-2):\n",
    "            if a > 0 and nums[a] == nums[a-1]:\n",
    "                continue\n",
    "\n",
    "            c = len(nums) - 1\n",
    "            for b in range(a+1, len(nums)-1):\n",
    "                if b > a+1 and nums[b] == nums[b-1]:\n",
    "                    continue\n",
    "\n",
    "                while b < c and nums[a] + nums[b] + nums[c] > 0:\n",
    "                    c -= 1\n",
    "                if b == c:\n",
    "                    break\n",
    "                if nums[a] + nums[b] + nums[c] == 0:\n",
    "                    res.append((nums[a], nums[b], nums[c]))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        s = []\n",
    "        if nums.count(0) >= 3:\n",
    "            s.append([0, 0, 0])\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] >= 0:\n",
    "                break\n",
    "            l1 = nums[i + 1:]\n",
    "            a = 0\n",
    "            b = n - i - 1 - 1\n",
    "            while a < b:\n",
    "                c = l1[a] + l1[b]\n",
    "                if -c > nums[i]:\n",
    "                    a += 1\n",
    "                elif -c < nums[i]:\n",
    "                    b -= 1\n",
    "                else:\n",
    "                    l2 = [-c, l1[a], l1[b]]\n",
    "                    l2.sort()\n",
    "                    if l2 not in s:\n",
    "                        s.append(l2)\n",
    "                    a += 1\n",
    "        return s\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                break\n",
    "\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            j = i + 1\n",
    "            k = len(nums) - 1\n",
    "            while j <k :\n",
    "                if nums[i] + nums[j] + nums[k] == 0:\n",
    "                    ans.append((nums[i], nums[j], nums[k]))\n",
    "                    while j < k and nums[j] == nums[j+1]:\n",
    "                        j += 1\n",
    "                    while j < k and nums[k] == nums[k-1]:\n",
    "                        k -= 1\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                elif nums[i] + nums[j] + nums[k] < 0:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        arr_target = [-i for i in nums[:-2]]\n",
    "        ret = []\n",
    "        tmp = []\n",
    "        for index, target in enumerate(arr_target):\n",
    "            left = index + 1\n",
    "            right = len(nums) - 1\n",
    "            while left < right:\n",
    "                l = nums[left]\n",
    "                r = nums[right]\n",
    "               #剪枝\n",
    "                if l > target:\n",
    "                    break\n",
    "                elif l + r == target:\n",
    "                    tmp = sorted([-target, l, r])\n",
    "                    if tmp not in ret:\n",
    "                        ret.append(tmp)\n",
    "                    left += 1\n",
    "                elif l + r > target:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left +=1\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        arr_target = [-i for i in nums[:-2]]\n",
    "        ret = []\n",
    "        tmp = []\n",
    "        for index, target in enumerate(arr_target):\n",
    "            left = index + 1\n",
    "            right = len(nums) - 1\n",
    "            while left < right:\n",
    "                l = nums[left]\n",
    "                r = nums[right]\n",
    "                # if l > target:\n",
    "                #     break\n",
    "                # elif l + r == target:\n",
    "                if l + r == target:\n",
    "                    tmp = sorted([-target, l, r])\n",
    "                    if tmp not in ret:\n",
    "                        ret.append(tmp)\n",
    "                    left += 1\n",
    "                elif l + r > target:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left +=1\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums = list(sorted(nums))\n",
    "        for i,a in enumerate(nums):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            target = 0 - a\n",
    "            left,right = i+1, len(nums)-1\n",
    "            while left < right:\n",
    "                if nums[left] + nums[right] == target:\n",
    "                    res.append((a,nums[left],nums[right]))\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                    while nums[right] == nums[right+1] and left < right:\n",
    "                        right -= 1\n",
    "                    while nums[left] == nums[left-1] and left < right:\n",
    "                        left += 1\n",
    "                elif nums[left] + nums[right] > target:\n",
    "                    right -=1\n",
    "                elif nums[left] + nums[right] < target:\n",
    "                    left += 1\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        nums = sorted(nums)\n",
    "        for i in range(n-2):\n",
    "            if nums[i] > 0:\n",
    "                break\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            l = i+1\n",
    "            r = n-1\n",
    "            while l < r:\n",
    "                if (s:= nums[i]+nums[l]+nums[r]) == 0:\n",
    "                    ans.append([nums[i], nums[l], nums[r]])\n",
    "                    while l < r and nums[l] == nums[l+1]: l += 1\n",
    "                    while l <  r and nums[r] == nums[r-1]: r -= 1\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                elif s > 0:\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 数组：双指针\n",
    "        ret = []\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                break\n",
    "            if i > 0 and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            left, right = i + 1, len(nums) - 1\n",
    "            while left < right:\n",
    "                sums = nums[i] + nums[left] + nums[right]\n",
    "                if sums > 0:\n",
    "                    right -= 1\n",
    "                elif sums < 0:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    ret.append([nums[i], nums[left], nums[right]])\n",
    "                    while left < right and nums[left] == nums[left + 1]:\n",
    "                        left += 1\n",
    "                    while left < right and nums[right] == nums[right - 1]:\n",
    "                        right -= 1\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        dic = defaultdict(int)       \n",
    "        for i in nums:\n",
    "            dic[i] += 1\n",
    "        nums = sorted(dic)             \n",
    "        for i, x in enumerate(nums):   \n",
    "            if x == 0 and dic[x] > 2:      \n",
    "                res.append([0, 0, 0])      \n",
    "            elif x != 0 and dic[x] > 1:    \n",
    "                if -(x<<1) in dic:          \n",
    "                    res.append([x, x, -(x<<1)])\n",
    "            if x < 0:                     \n",
    "                y_z = -x                                       \n",
    "                z_id = bisect.bisect_right(nums, y_z>>1, i+1) # 求得 y_z//2 的下标\n",
    "                for z in nums[z_id:]:                          \n",
    "                    y = y_z - z\n",
    "                    if y > x and y in dic:\n",
    "                        res.append([x, y, z])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums) >= 3 and len(set(nums)) == 1 and nums[0] == 0: return [nums[:3]]\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        for i in range(n-2):\n",
    "            x = nums[i]\n",
    "            if x == nums[i-1]:\n",
    "                continue\n",
    "            if x + nums[i+1] + nums[i+2] > 0:\n",
    "                break\n",
    "            if x + nums[-2] + nums[-1] < 0:\n",
    "                continue\n",
    "            j = i + 1\n",
    "            k = n - 1\n",
    "            while j < k:\n",
    "                s = x + nums[j] + nums[k]\n",
    "                if s > 0:\n",
    "                    k -= 1\n",
    "                elif s < 0:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    ans.append([x, nums[j], nums[k]])\n",
    "                    j += 1\n",
    "                    while j < k and nums[j] == [j-1]:\n",
    "                        j += 1\n",
    "                    k -= 1\n",
    "                    while k > j and nums[k] == nums[k+1]:\n",
    "                        k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return []\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        for i in range(0, n - 2):\n",
    "            if i > 0 and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            j = i + 1\n",
    "            k = n - 1\n",
    "            while j < k:\n",
    "                if nums[i] + nums[j] + nums[k] == 0:\n",
    "                    res.append([nums[i], nums[j], nums[k]])\n",
    "                    while j < k and nums[k] == nums[k - 1]:\n",
    "                        k -= 1\n",
    "                    while j < k and nums[j] == nums[j + 1]:\n",
    "                        j += 1\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                elif nums[i] + nums[k] + nums[j] < 0:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    k -= 1\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法一\n",
    "# 标签：数组遍历\n",
    "# 首先对数组进行排序，排序后固定一个数 nums[i]nums[i]nums[i]，再使用左右指针指向 nums[i]nums[i]nums[i]后面的两端，数字分别为 nums[L]nums[L]nums[L] 和 nums[R]nums[R]nums[R]，计算三个数的和 sumsumsum 判断是否满足为 000，满足则添加进结果集\n",
    "# 如果 nums[i]nums[i]nums[i]大于 000，则三数之和必然无法等于 000，结束循环\n",
    "# 如果 nums[i]nums[i]nums[i] == nums[i−1]nums[i-1]nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过\n",
    "# 当 sumsumsum == 000 时，nums[L]nums[L]nums[L] == nums[L+1]nums[L+1]nums[L+1] 则会导致结果重复，应该跳过，L++\n",
    "# 当 sumsumsum == 000 时，nums[R]nums[R]nums[R] == nums[R−1]nums[R-1]nums[R−1] 则会导致结果重复，应该跳过，R−−\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        if not nums or len(nums) < 3:\n",
    "            return []\n",
    "        \n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        for i in range(0, len(nums)):\n",
    "            if nums[i] > 0: # 因为排序过，所以第一个数》0了，sum三数之和肯定大于0了\n",
    "                break\n",
    "            if i > 0 and nums[i] == nums[i-1]: # 去重第一个数\n",
    "                continue\n",
    "            \n",
    "            # 左右指针从两边向中间对齐\n",
    "            l = i + 1\n",
    "            r = len(nums) - 1\n",
    "            while l < r:\n",
    "                sum = nums[i] + nums[l] + nums[r]\n",
    "                left = nums[l]\n",
    "                right = nums[r]\n",
    "                if sum == 0:\n",
    "                    ans.append([nums[i], nums[l], nums[r]])\n",
    "                    # 去重第二、第三个数\n",
    "                    while l < r and nums[l] == left:\n",
    "                        l += 1\n",
    "                    while l < r and nums[r] == right:\n",
    "                        r -= 1\n",
    "                    # l += 1\n",
    "                    # r -= 1\n",
    "                elif sum < 0:\n",
    "                    l += 1\n",
    "                elif sum > 0:\n",
    "                    r -= 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "# 方法二：labuladong 排序+双指针,可以通过。但是这个方法用在4Sum，无法通过\n",
    "# class Solution:\n",
    "#     def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "#         nums.sort()\n",
    "#         # n 为 3，从 nums[0] 开始计算和为 0 的三元组\n",
    "#         # n 填写想求的是几数之和，start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和\n",
    "#         ans = self.nSumTarget(nums, 3, 0, 0)\n",
    "\n",
    "#         return ans\n",
    "    \n",
    "#     def nSumTarget(self, nums, n, start, target):\n",
    "#         if len(nums) < n:\n",
    "#             return []\n",
    "#         if n < 2:# 至少是2Sum\n",
    "#             return []\n",
    "        \n",
    "#         ans = []\n",
    "        \n",
    "#         if n == 2: # 就是最好写的两数之和\n",
    "#         # 双指针那一套操作\n",
    "#             l, r = start, len(nums) - 1\n",
    "#             while l < r:\n",
    "#                 sum_ = nums[l] + nums[r]\n",
    "#                 left, right = nums[l], nums[r]\n",
    "#                 if sum_ == target:\n",
    "#                     ans.append([left, right])\n",
    "#                     while l < r and nums[l] == left:\n",
    "#                         l += 1\n",
    "#                     while l < r and nums[r] == right:\n",
    "#                         r -= 1\n",
    "#                 elif sum_ > target:\n",
    "#                     while l < r and nums[r] == right:\n",
    "#                         r -= 1\n",
    "#                 elif sum_ < target:\n",
    "#                     while l < r and nums[l] == left:\n",
    "#                         l += 1\n",
    "#         else:\n",
    "#             # 大于2Sum的，先求n-1\n",
    "#             # n > 2 时，递归计算 (n-1)Sum 的结果，就想象成3Sum的，比较好理解\n",
    "#             for i in range(start, len(nums)):\n",
    "#                 if i > 0 and nums[i] == nums[i-1]: #去重\n",
    "#                     continue\n",
    "\n",
    "#                 target_ = target - nums[i]\n",
    "#                 sub = self.nSumTarget(nums, n - 1, i + 1, target_)\n",
    "#                 for arr in sub:\n",
    "#                     # (n-1)Sum 加上 nums[i] 就是 nSum\n",
    "#                     arr.append(nums[i])\n",
    "#                     ans.append(arr) # 这里的ans是指最外层的ans，是[]。递归时候最里层的ans被用掉了，不为空。但代码跑到这时，用的是最外层的ans，为[]\n",
    "        \n",
    "#         return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for first in range(n):\n",
    "            if first > 0 and nums[first] == nums[first-1]:\n",
    "                continue\n",
    "            third = n - 1\n",
    "            target = -nums[first]\n",
    "\n",
    "            for second in range(first+1, n):\n",
    "                if second > first + 1 and nums[second] == nums[second-1]:\n",
    "                    continue\n",
    "                while second < third and nums[second] + nums[third] > target:\n",
    "                    third -= 1\n",
    "                if second == third:\n",
    "                    break\n",
    "                if nums[second] + nums[third] == target:\n",
    "                    ans.append([nums[first], nums[second], nums[third]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n, ans = len(nums), []\n",
    "        pre_i = pre_j = 114514\n",
    "        nums.sort()\n",
    "        for i in range(n-2):\n",
    "            ni = nums[i]\n",
    "            if ni == pre_i:\n",
    "                continue\n",
    "            pre_i = ni\n",
    "\n",
    "            for j in range(i+1, n-1):\n",
    "                nj = nums[j]\n",
    "                if nj == pre_j:\n",
    "                    continue\n",
    "                pre_j = nj\n",
    "                k = bisect.bisect_left(nums, -ni-nj, lo=j+1)\n",
    "                if k < n and ni+nj+nums[k] == 0:\n",
    "                    ans.append([ni, nj, nums[k]])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        if l<3:\n",
    "            return []\n",
    "        rs = []\n",
    "        for i in range(l-2):\n",
    "            a = nums[i]\n",
    "            if a>0:\n",
    "                break\n",
    "            if i>0 and a==nums[i-1]:  # 去重\n",
    "                continue\n",
    "            st, ed = i+1, l-1\n",
    "\n",
    "            while st<ed:\n",
    "                b, c = nums[st], nums[ed]\n",
    "                if a+b+c==0:\n",
    "                    rs.append([a, b, c])\n",
    "                    st += 1\n",
    "                    ed -= 1\n",
    "                    while st<ed and nums[st]==nums[st-1]:\n",
    "                        st += 1\n",
    "                    while st<ed and nums[ed]==nums[ed+1]:\n",
    "                        ed -= 1\n",
    "                elif a+b+c<0:\n",
    "                    st += 1\n",
    "                else:\n",
    "                     ed -= 1\n",
    "        return rs\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            a = nums[i]\n",
    "            l, r = i+1, len(nums)-1\n",
    "            \n",
    "            while l < r:\n",
    "                if l < r and l > i+1 and nums[l] == nums[l-1]:\n",
    "                    l += 1\n",
    "                    continue\n",
    "                if l < r and r < len(nums)-1 and nums[r] == nums[r+1]:\n",
    "                    r -= 1\n",
    "                    continue\n",
    "                b, c = nums[l], nums[r]\n",
    "                if a+b+c == 0:\n",
    "                    res.append([a, b, c])\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                elif a+b+c < 0:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            l,r = i+1,n-1\n",
    "            while l<r:\n",
    "                if nums[l]+nums[r]==-nums[i]:\n",
    "                    t = [nums[i],nums[l],nums[r]]\n",
    "                    if t not in(res):\n",
    "                        res.append(t)\n",
    "                    l+=1\n",
    "                    r-=1\n",
    "                elif nums[l]+nums[r]<-nums[i]:\n",
    "                    l+=1\n",
    "                else:\n",
    "                    r-=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        for i in range(n-2):\n",
    "            a = nums[i]\n",
    "            if i > 0 and a == nums[i-1]:\n",
    "                continue\n",
    "            if a + nums[i+1] + nums[i+2] > 0:\n",
    "                break\n",
    "            if a + nums[-1] + nums[-2] < 0:\n",
    "                continue\n",
    "            j, k = i+1, n-1\n",
    "            while j < k:\n",
    "                b, c = nums[j], nums[k]\n",
    "                if j > i+1 and b == nums[j-1]:\n",
    "                    j += 1\n",
    "                    continue\n",
    "                if k < n-1 and c == nums[k+1]:\n",
    "                    k -= 1\n",
    "                    continue\n",
    "                s = a + b + c\n",
    "                if s < 0:\n",
    "                    j += 1\n",
    "                elif s > 0:\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    ans.append([a, b, c])\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if i>0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            l, r = i+1, n-1\n",
    "            while l<r:\n",
    "                if l<r and nums[i] + nums[l]+nums[r] == 0:\n",
    "                    res.append([nums[i], nums[l], nums[r]])\n",
    "                    l+=1\n",
    "                    r-=1\n",
    "                    while l<r and nums[l] == nums[l-1]:\n",
    "                        l+=1\n",
    "                    while l<r and nums[r]>nums[r+1]:\n",
    "                        r-=1\n",
    "                elif l<r and nums[i] + nums[l]+nums[r] < 0:\n",
    "                    l += 1\n",
    "                elif l<r and nums[i] + nums[l]+nums[r] > 0:\n",
    "                    r -= 1\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        ans=[]\n",
    "        for i in range(n-2):\n",
    "            if i>0 and nums[i]==nums[i-1]:\n",
    "                continue\n",
    "            j,k=i+1,n-1\n",
    "            while j<k:\n",
    "                if j>i+1 and nums[j]==nums[j-1]:\n",
    "                    j+=1\n",
    "                    continue\n",
    "                if nums[j]+nums[k]==-nums[i]:\n",
    "                    if (tmp:=[nums[i],nums[j],nums[k]]) not in ans:\n",
    "                        ans.append(tmp)\n",
    "                    j+=1\n",
    "                    k-=1\n",
    "                elif nums[j]+nums[k]>-nums[i]:\n",
    "                    k-=1\n",
    "                else:\n",
    "                    j+=1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        ans=[]\n",
    "        for i in range(n-2):\n",
    "            j,k=i+1,n-1\n",
    "            while j<k:\n",
    "                if nums[j]+nums[k]==-nums[i]:\n",
    "                    if (tmp:=[nums[i],nums[j],nums[k]]) not in ans:\n",
    "                        ans.append(tmp)\n",
    "                    j+=1\n",
    "                    k-=1\n",
    "                elif nums[j]+nums[k]>-nums[i]:\n",
    "                    k-=1\n",
    "                else:\n",
    "                    j+=1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if nums[i] > 0:\n",
    "                return ans  #返回ans而不是[]\n",
    "            if i > 0 and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            left, right = i + 1, n - 1\n",
    "            while left < right:\n",
    "                sums = nums[i] + nums[left] + nums[right]\n",
    "                if sums > 0:\n",
    "                    right -= 1\n",
    "                elif sums < 0:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    ans.append([nums[i], nums[left], nums[right]])\n",
    "                    while left < right and nums[left + 1] == nums[left]:\n",
    "                        left += 1\n",
    "                    while left < right and nums[right - 1] == nums[right]:\n",
    "                        right -= 1\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for cur in range(len(nums)):\n",
    "            # 对cur进行去重\n",
    "            if nums[cur] > 0:\n",
    "                return res\n",
    "            if cur >= 1 and nums[cur] == nums[cur - 1]:\n",
    "                continue\n",
    "            left = cur + 1\n",
    "            right = n - 1\n",
    "            while left < right:\n",
    "                total = nums[cur] + nums[left] + nums[right]\n",
    "                if total > 0 :\n",
    "                    right -= 1\n",
    "                elif total < 0 :\n",
    "                    left += 1\n",
    "                else:\n",
    "                    res.append([nums[cur],nums[left],nums[right]]) #收集符合条件的数据\n",
    "                    # 对left 和right 进行去重\n",
    "                    while left < right and nums[left + 1] == nums[left]:\n",
    "\n",
    "                        left += 1\n",
    "                    while left < right and nums[right-1] == nums[right]:\n",
    "\n",
    "                        right -= 1\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans =[]\n",
    "        for i in range(0,n-2):\n",
    "            target = -nums[i]\n",
    "\n",
    "            if i>0 and nums[i]==nums[i-1]:\n",
    "                continue # 目标值相同则不重复搜索\n",
    "            left = i+1\n",
    "            right = n-1\n",
    "\n",
    "            while left<right:\n",
    "                s=nums[left]+nums[right]\n",
    "                if s==target:\n",
    "                    ans.append([nums[i], nums[left], nums[right]])\n",
    "                \n",
    "                    while left<right and nums[left]==nums[left+1]:\n",
    "                        left+=1\n",
    "                    while left<right and nums[right]==nums[right-1]:\n",
    "                        right-=1\n",
    "                    left+=1  # 跳出重复范围继续搜索\n",
    "                    right-=1\n",
    "\n",
    "                # 为了最外层while循环能正常终止，以下这两行不要忘记\n",
    "                if s>target:\n",
    "                    right-=1\n",
    "                if s<target:\n",
    "                    left+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        #print(nums)\n",
    "        def find(l,r,target):\n",
    "            if l>r:\n",
    "                return r\n",
    "            now = (l+r) // 2\n",
    "            if nums[now] == target:\n",
    "                return now\n",
    "            if nums[now] < target:\n",
    "                return find(now+1,r,target)\n",
    "            if nums[now] > target:\n",
    "                return find(l,now-1,target)\n",
    "        res = []\n",
    "        i = 0\n",
    "        while(i<n-2):\n",
    "            r = n-1\n",
    "            j = i+1\n",
    "            while(j<n-1):\n",
    "                target = 0-(nums[i]+nums[j])\n",
    "                #print(target, nums[i], nums[j])\n",
    "                l = j+1\n",
    "                if nums[r] >= target and nums[l] <= target and l<=r:\n",
    "                    r = find(l,r,target)\n",
    "                    #print(r,nums[r])\n",
    "                    if nums[r] == target:\n",
    "                        res.append([nums[i],nums[j],nums[r]])\n",
    "                        r -= 1\n",
    "                j += 1\n",
    "                while(j<n and nums[j-1]==nums[j]):\n",
    "                    j += 1\n",
    "            i += 1\n",
    "            while(i<n and nums[i-1]==nums[i]):\n",
    "                i += 1\n",
    "        return res    \n",
    "        '''\n",
    "        n = len(nums)\n",
    "        s = {}\n",
    "        for num in nums:\n",
    "            if num in s.keys():\n",
    "                s[num] += 1\n",
    "            else:\n",
    "                s[num] = 1\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if s[nums[i]] == 0:\n",
    "                continue\n",
    "            s[nums[i]] -= 1\n",
    "            s_tmp = s.copy()\n",
    "            for j in range(i+1,n):\n",
    "                if s_tmp[nums[j]] == 0:\n",
    "                    continue\n",
    "                s_tmp[nums[j]] -= 1\n",
    "                target = (0-nums[i]-nums[j])\n",
    "                if s_tmp.get(target, 0) > 0:\n",
    "                    res.append([nums[i], nums[j], target])\n",
    "                s_tmp[nums[j]] = 0\n",
    "            s[nums[i]] = 0\n",
    "        return res\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        ans = list()\n",
    "        n = len(nums)\n",
    "\n",
    "        for first in range(n):\n",
    "            if first > 0 and nums[first] == nums[first - 1]:\n",
    "                continue\n",
    "\n",
    "            third = n - 1\n",
    "            target = -nums[first]\n",
    "            for second in range(first + 1, n):\n",
    "                if second > first + 1 and nums[second] == nums[second - 1]:\n",
    "                    continue\n",
    "\n",
    "                while second < third and nums[second] + nums[third] > target:\n",
    "                    third -= 1\n",
    "\n",
    "                if second == third:\n",
    "                    break\n",
    "                if nums[second] + nums[third] == target:\n",
    "                    ans.append([nums[first], nums[second], nums[third]])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        for first in range(n):\n",
    "            if first > 0 and nums[first] == nums[first - 1]:\n",
    "                continue\n",
    "            target = -nums[first]\n",
    "            third = n - 1\n",
    "            for second in range(first + 1, n):\n",
    "                if second > first + 1 and nums[second] == nums[second - 1]:\n",
    "                    continue\n",
    "                while third > second and nums[second] + nums[third] > target:\n",
    "                    third -= 1\n",
    "                if second == third:\n",
    "                    break\n",
    "                if nums[third] + nums[second] == target:\n",
    "                    ans.append([nums[first], nums[second], nums[third]])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        hash_map = {}\n",
    "        for i in range(n):\n",
    "            hash_map[nums[i]] = i\n",
    "        results = []\n",
    "        # sets = set()\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if - nums[i] - nums[j] in hash_map and hash_map[- nums[i] - nums[j]] != i and hash_map[- nums[i] - nums[j]] != j:\n",
    "                    # ele = set([nums[i], nums[j], hash_map[- nums[i] - nums[j]]])\n",
    "                    ele = sorted([nums[i], nums[j], nums[hash_map[- nums[i] - nums[j]]]])\n",
    "                    if ele not in results:\n",
    "                        results.append(ele)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        def find(l,r,target):\n",
    "            if l>r:\n",
    "                return r\n",
    "            now = (l+r) // 2\n",
    "            if nums[now] == target:\n",
    "                return now\n",
    "            if nums[now] < target:\n",
    "                return find(now+1,r,target)\n",
    "            if nums[now] > target:\n",
    "                return find(l,now-1,target)\n",
    "        res = []\n",
    "        i = 0\n",
    "        while(i<n-2):\n",
    "            if nums[i] + nums[i+1] + nums[i+2] > 0:\n",
    "                break\n",
    "            r = n-1\n",
    "            j = i+1\n",
    "            while(j<n-1):\n",
    "                target = 0-(nums[i]+nums[j])\n",
    "                l = j+1\n",
    "                if nums[l] > target:\n",
    "                    break\n",
    "                if nums[r] >= target and nums[l] <= target and l<=r:\n",
    "                    r = find(l,r,target)\n",
    "                    if nums[r] == target:\n",
    "                        res.append([nums[i],nums[j],nums[r]])\n",
    "                        r -= 1\n",
    "                j += 1\n",
    "                while(j<n and nums[j-1]==nums[j]):\n",
    "                    j += 1\n",
    "            i += 1\n",
    "            while(i<n and nums[i-1]==nums[i]):\n",
    "                i += 1\n",
    "        return res    \n",
    "        '''\n",
    "        n = len(nums)\n",
    "        s = {}\n",
    "        for num in nums:\n",
    "            if num in s.keys():\n",
    "                s[num] += 1\n",
    "            else:\n",
    "                s[num] = 1\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if s[nums[i]] == 0:\n",
    "                continue\n",
    "            s[nums[i]] -= 1\n",
    "            s_tmp = s.copy()\n",
    "            for j in range(i+1,n):\n",
    "                if s_tmp[nums[j]] == 0:\n",
    "                    continue\n",
    "                s_tmp[nums[j]] -= 1\n",
    "                target = (0-nums[i]-nums[j])\n",
    "                if s_tmp.get(target, 0) > 0:\n",
    "                    res.append([nums[i], nums[j], target])\n",
    "                s_tmp[nums[j]] = 0\n",
    "            s[nums[i]] = 0\n",
    "        return res\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]: \n",
    "        d=Counter(nums)\n",
    "        ans=list(d.keys())\n",
    "        ans.sort()\n",
    "        n=len(ans)\n",
    "\n",
    "        ret=[]\n",
    "        print(ans)\n",
    "        for i in range(n):\n",
    "            x=n-1\n",
    "            if ans[i]>=0:\n",
    "                break\n",
    "            if d[ans[i]]>1 and d.get(-(2*ans[i]),0):\n",
    "                ret.append([ans[i],ans[i],-(2*ans[i])])\n",
    "            for j in range(i+1,n):\n",
    "                if ans[i]+ans[j]>0:\n",
    "                    break\n",
    "                if d[ans[j]]>1 and 2*ans[j]+ans[i]==0:\n",
    "                    ret.append([ans[i],ans[j],ans[j]])\n",
    "                while x>j and ans[j]+ans[i]>-ans[x]:\n",
    "                    x-=1\n",
    "                if x==j:\n",
    "                    break\n",
    "                if ans[i]+ans[j]+ans[x]==0:\n",
    "                    ret.append([ans[i],ans[j],ans[x]])\n",
    "        if d.get(0,0)>2:\n",
    "            ret.append([0,0,0])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        def process(nums,tar):\n",
    "            i,j = 0,len(nums) - 1\n",
    "            result = []\n",
    "            hashmap = set()\n",
    "            while i < j:\n",
    "                if nums[i] in hashmap:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                if nums[j] in hashmap:\n",
    "                    j -= 1\n",
    "                    continue\n",
    "\n",
    "                cur = nums[i] + nums[j]\n",
    "                if cur > tar:\n",
    "                    j -= 1\n",
    "                elif cur < tar:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    if nums[i] not in hashmap or nums[j] not in hashmap:\n",
    "                        result.append([nums[i],nums[j],-1*tar])\n",
    "                        hashmap.add(nums[i])\n",
    "                        hashmap.add(nums[j])\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "            return result\n",
    "        \n",
    "        nums.sort()\n",
    "        result = []\n",
    "        last = None\n",
    "        while len(nums) > 2:\n",
    "\n",
    "            tar = nums.pop() \n",
    "            if last == tar:\n",
    "                continue\n",
    "            last = tar\n",
    "            tp = process(nums,-1*tar)\n",
    "            if tp:\n",
    "                result.extend(tp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        l = len(nums)\n",
    "        if l <= 2:\n",
    "            return []\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        next = [l] * l\n",
    "        last = [-1] * l\n",
    "        for i in range(l - 2, -1, -1):\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                next[i] = next[i + 1]\n",
    "            else:\n",
    "                next[i] = i + 1\n",
    "        for i in range(1, l):\n",
    "            if nums[i] == nums[i - 1]:\n",
    "                last[i] = last[i - 1]\n",
    "            else:\n",
    "                last[i] = i - 1\n",
    "        i, j, k = 0, 1, l - 1\n",
    "        while True:\n",
    "            if nums[i] + nums[j] + nums[k] < 0:\n",
    "                j = next[j]\n",
    "                if j == k:\n",
    "                    j += 1\n",
    "            elif nums[i] + nums[j] + nums[k] > 0:\n",
    "                k = last[k]\n",
    "                if k == j:\n",
    "                    k -= 1\n",
    "            elif nums[i] + nums[j] + nums[k] == 0:\n",
    "                res.append([nums[i], nums[j], nums[k]])\n",
    "                j = next[j]\n",
    "            if j > k:\n",
    "                i = next[i]\n",
    "                j = i + 1\n",
    "                k = l - 1\n",
    "                if i >= l - 2:\n",
    "                    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        if n < 3:return []\n",
    "        dic = Counter(nums)\n",
    "        ans = set()\n",
    "        nums.sort()\n",
    "        for i in range(n-2):\n",
    "            for j in range(i+1,n-1):\n",
    "                t = 0 - nums[i] - nums[j]\n",
    "                if t<nums[j]:\n",
    "                    break\n",
    "                elif t in dic:\n",
    "                    if t == 0:\n",
    "                        if dic[0]>2:\n",
    "                            ans.add((0,0,0))\n",
    "                    elif t == nums[j]:\n",
    "                        if dic[t]>1:\n",
    "                            ans.add((nums[i],nums[j],t))\n",
    "                    else:\n",
    "                        ans.add((nums[i],nums[j],t))\n",
    "        return [list(i) for i in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        sorted_nums = sorted(nums)\n",
    "        n = len(nums) \n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            target = - sorted_nums[i]\n",
    "            start = i + 1\n",
    "            end = n - 1\n",
    "            while start < end:\n",
    "                temp = sorted_nums[start] + sorted_nums[end]\n",
    "                if  temp == target:\n",
    "                    temp_res = [-target, sorted_nums[start], sorted_nums[end]]\n",
    "                    if temp_res not in res:\n",
    "                        res.append(temp_res)\n",
    "                    end -= 1\n",
    "                elif temp > target:\n",
    "                    end -= 1\n",
    "                else: \n",
    "                    start += 1\n",
    "            \n",
    "            \n",
    "            # print(temp, start, end)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        #回溯时间太长，\n",
    "        # ans = []\n",
    "        # p = []\n",
    "        # nums.sort()\n",
    "        # used = [0]*len(nums)\n",
    "        # #回溯+这里的元素不可重复，因此设置一个索引\n",
    "        # def backtrac(num_arry,index,path,target):\n",
    "        #     if len(path) == 3 and target==0:\n",
    "        #         ans.append(path[:])\n",
    "        #         return\n",
    "            \n",
    "        #     if len(path)>3 or index>=len(num_arry):\n",
    "        #         return\n",
    "        #     if used[index]==1:\n",
    "        #         return \n",
    "        #     #我这里的情况是元素被重复使用了\n",
    "        #     for i in range(index,len(num_arry)):#这里如何约束\n",
    "        #         path.append(num_arry[i])\n",
    "        #         target -= num_arry[i]\n",
    "        #         used[i] = 1\n",
    "        #         backtrac(num_arry,i+1,path,target)\n",
    "        #         used[i] = 0\n",
    "        #         target += num_arry[i]\n",
    "        #         path.pop()\n",
    "\n",
    "        # #注意上面的for里面不返回，只有在符合条件时才返回\n",
    "        # backtrac(nums,0,p,0)\n",
    "        # #去重\n",
    "        # new_ans = []\n",
    "        # for value in ans:\n",
    "        #     if value not in new_ans:\n",
    "        #         new_ans.append(value)\n",
    "        # return new_ans\n",
    "\n",
    "        #所有查收元素和的问题都是双指针+排序\n",
    "        #和大于目标时，right--;和小于目标时，left ++\n",
    "        #三个数字时，迭代计算\n",
    "        #是否可以固定一个，然后left是他后面的位置\n",
    "        nums.sort()\n",
    "        #从0开始计算和为0的三元组\n",
    "        return self.nsumtarget(nums,3,0,0)#长度为3，开始位置为0，和为0\n",
    "\n",
    "    def nsumtarget(self,nums,n,index,target):\n",
    "        #判断一些可以直接排除的情况\n",
    "        sz = len(nums)\n",
    "        res = []\n",
    "        if n<2 or sz<n:\n",
    "            return res\n",
    "        #如果只只需查找两个\n",
    "        if n==2:\n",
    "            left = index\n",
    "            right = sz-1\n",
    "            while left<right:\n",
    "                sum_ = nums[left]+nums[right]\n",
    "                lv  = nums[left]\n",
    "                rv = nums[right]\n",
    "                #判断情况，觉得指针的移动情况\n",
    "                if sum_ == target:\n",
    "                    res.append([nums[left],nums[right]])\n",
    "                    #继续移动\n",
    "                    while left<right and nums[left]==lv:\n",
    "                        left += 1\n",
    "                    while left<right and nums[right] ==  rv:\n",
    "                        right -=1\n",
    "                elif sum_ < target:\n",
    "                    while left<right and nums[left] == lv:#跳过重复的元素\n",
    "                        left+=1\n",
    "                elif sum_>target:\n",
    "                    while left<right and nums[right]==rv:\n",
    "                        right -=1\n",
    "        else:\n",
    "            #元组长度大于2时，需要递归n-1的长度，然后添加上当前的值\n",
    "            for i in range(index,sz):#固定一个查找值\n",
    "                if i>0 and nums[i]==nums[i-1]:\n",
    "                    continue         \n",
    "                sub = self.nsumtarget(nums,n-1,i+1,target-nums[i])\n",
    "                for arr in sub:\n",
    "                    arr.append(nums[i])\n",
    "                    res.append(arr)\n",
    "\n",
    "        return res\n",
    "                \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法一\n",
    "# 标签：数组遍历\n",
    "# 首先对数组进行排序，排序后固定一个数 nums[i]nums[i]nums[i]，再使用左右指针指向 nums[i]nums[i]nums[i]后面的两端，数字分别为 nums[L]nums[L]nums[L] 和 nums[R]nums[R]nums[R]，计算三个数的和 sumsumsum 判断是否满足为 000，满足则添加进结果集\n",
    "# 如果 nums[i]nums[i]nums[i]大于 000，则三数之和必然无法等于 000，结束循环\n",
    "# 如果 nums[i]nums[i]nums[i] == nums[i−1]nums[i-1]nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过\n",
    "# 当 sumsumsum == 000 时，nums[L]nums[L]nums[L] == nums[L+1]nums[L+1]nums[L+1] 则会导致结果重复，应该跳过，L++\n",
    "# 当 sumsumsum == 000 时，nums[R]nums[R]nums[R] == nums[R−1]nums[R-1]nums[R−1] 则会导致结果重复，应该跳过，R−−\n",
    "\n",
    "# class Solution:\n",
    "#     def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "#         if not nums or len(nums) < 3:\n",
    "#             return []\n",
    "        \n",
    "#         ans = []\n",
    "#         nums.sort()\n",
    "#         for i in range(0, len(nums)):\n",
    "#             if nums[i] > 0: # 因为排序过，所以第一个数》0了，sum三数之和肯定大于0了\n",
    "#                 break\n",
    "#             if i > 0 and nums[i] == nums[i-1]: # 去重第一个数\n",
    "#                 continue\n",
    "            \n",
    "#             # 左右指针从两边向中间对齐\n",
    "#             l = i + 1\n",
    "#             r = len(nums) - 1\n",
    "#             while l < r:\n",
    "#                 sum = nums[i] + nums[l] + nums[r]\n",
    "#                 left = nums[l]\n",
    "#                 right = nums[r]\n",
    "#                 if sum == 0:\n",
    "#                     ans.append([nums[i], nums[l], nums[r]])\n",
    "#                     # 去重第二、第三个数\n",
    "#                     while l < r and nums[l] == left:\n",
    "#                         l += 1\n",
    "#                     while l < r and nums[r] == right:\n",
    "#                         r -= 1\n",
    "#                     # l += 1\n",
    "#                     # r -= 1\n",
    "#                 elif sum < 0:\n",
    "#                     l += 1\n",
    "#                 elif sum > 0:\n",
    "#                     r -= 1\n",
    "#         return ans\n",
    "\n",
    "\n",
    "# 方法二：labuladong 排序+双指针\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        # n 为 3，从 nums[0] 开始计算和为 0 的三元组\n",
    "        # n 填写想求的是几数之和，start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和\n",
    "        ans = self.nSumTarget(nums, 3, 0, 0)\n",
    "\n",
    "        return ans\n",
    "    \n",
    "    def nSumTarget(self, nums, n, start, target):\n",
    "        if len(nums) < n:\n",
    "            return []\n",
    "        if n < 2:# 至少是2Sum\n",
    "            return []\n",
    "        \n",
    "        ans = []\n",
    "        \n",
    "        if n == 2: # 就是最好写的两数之和\n",
    "        # 双指针那一套操作\n",
    "            l, r = start, len(nums) - 1\n",
    "            while l < r:\n",
    "                sum_ = nums[l] + nums[r]\n",
    "                left, right = nums[l], nums[r]\n",
    "                if sum_ == target:\n",
    "                    ans.append([left, right])\n",
    "                    while l < r and nums[l] == left:\n",
    "                        l += 1\n",
    "                    while l < r and nums[r] == right:\n",
    "                        r -= 1\n",
    "                elif sum_ > target:\n",
    "                    while l < r and nums[r] == right:\n",
    "                        r -= 1\n",
    "                elif sum_ < target:\n",
    "                    while l < r and nums[l] == left:\n",
    "                        l += 1\n",
    "        else:\n",
    "            # 大于2Sum的，先求n-1\n",
    "            # n > 2 时，递归计算 (n-1)Sum 的结果，就想象成3Sum的，比较好理解\n",
    "            for i in range(start, len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i-1]: #去重\n",
    "                    continue\n",
    "\n",
    "                target_ = target - nums[i]\n",
    "                sub = self.nSumTarget(nums, n - 1, i + 1, target_)\n",
    "                for arr in sub:\n",
    "                    # (n-1)Sum 加上 nums[i] 就是 nSum\n",
    "                    arr.append(nums[i])\n",
    "                    ans.append(arr) # 这里的ans是指最外层的ans，是[]。递归时候最里层的ans被用掉了，不为空。但代码跑到这时，用的是最外层的ans，为[]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        def process(nums,tar):\n",
    "            i,j = 0,len(nums) - 1\n",
    "            result = []\n",
    "\n",
    "            while i < j:\n",
    "                if i > 0 and nums[i] ==nums[i - 1]:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                if j < len(nums) - 1 and nums[j] == nums[j + 1]:\n",
    "                    j -= 1\n",
    "                    continue\n",
    "                cur = nums[i] + nums[j]\n",
    "                if cur > tar:\n",
    "                    j -= 1\n",
    "                elif cur < tar:\n",
    "                    i += 1\n",
    "                else:\n",
    "\n",
    "                    result.append([nums[i],nums[j],-1*tar])\n",
    "\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "            return result\n",
    "        \n",
    "        nums.sort()\n",
    "        result = []\n",
    "        last = None\n",
    "        while len(nums) > 2:\n",
    "\n",
    "            tar = nums.pop() \n",
    "            if last == tar:\n",
    "                continue\n",
    "            last = tar\n",
    "            tp = process(nums,-1*tar)\n",
    "            if tp:\n",
    "                result.extend(tp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        if not nums:\n",
    "            return res\n",
    "        \n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(n):\n",
    "            target = - nums[i]\n",
    "            hash = dict()\n",
    "            for j in range(i+1, n):\n",
    "                temp = target - nums[j]\n",
    "                if temp in hash:\n",
    "                    ans = [nums[i],nums[j], temp]\n",
    "                    # ans.sort()\n",
    "                    if ans not in res:\n",
    "                        res.append(ans)     \n",
    "                hash[nums[j]] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            # a + b = -c\n",
    "            if i - 1 >= 0 and nums[i] == nums[i - 1]:continue\n",
    "            target = -nums[i]\n",
    "            left = i + 1\n",
    "            right = n - 1\n",
    "            while left < right:\n",
    "                temp = nums[left] + nums[right]\n",
    "                if temp < target:left += 1\n",
    "                elif temp > target:right -= 1\n",
    "                else:\n",
    "                    ret.append([-target,nums[left],nums[right]])\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                    #这里也需要去重\n",
    "                    while left < right and nums[left] == nums[left - 1]:left += 1\n",
    "                    while left < right and nums[right] == nums[right + 1]:right -= 1\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def twosum(nums,start,target):\n",
    "    res = []\n",
    "    left,right = start,len(nums)-1\n",
    "    while left < right:\n",
    "        left_num, right_num = nums[left], nums[right]\n",
    "        two_sum = left_num + right_num\n",
    "        if two_sum > target:\n",
    "            right -= 1\n",
    "            while left < right and nums[right] == right_num:\n",
    "                right -= 1\n",
    "        elif two_sum < target:\n",
    "            left += 1\n",
    "            while left < right and nums[left] == left_num:\n",
    "                left += 1\n",
    "        elif two_sum == target:\n",
    "            res.append([nums[left],nums[right]])\n",
    "            while left < right and nums[left] == left_num:\n",
    "                left += 1\n",
    "            while left < right and nums[right] == right_num:\n",
    "                right -= 1\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        output = []\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            temp_res = twosum(nums,i+1,0-nums[i])\n",
    "\n",
    "            for item in temp_res:\n",
    "                item.append(nums[i])\n",
    "                output.append(item)\n",
    "            while i < len(nums) - 1 and nums[i] == nums[i + 1]:\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return output\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        s = {}\n",
    "        for num in nums:\n",
    "            if num in s.keys():\n",
    "                s[num] += 1\n",
    "            else:\n",
    "                s[num] = 1\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if s[nums[i]] == 0:\n",
    "                continue\n",
    "            s[nums[i]] -= 1\n",
    "            s_tmp = s.copy()\n",
    "            for j in range(i+1,n):\n",
    "                if s_tmp[nums[j]] == 0:\n",
    "                    continue\n",
    "                s_tmp[nums[j]] -= 1\n",
    "                target = (0-nums[i]-nums[j])\n",
    "                if s_tmp.get(target, 0) > 0:\n",
    "                    res.append([nums[i], nums[j], target])\n",
    "                s_tmp[nums[j]] = 0\n",
    "            s[nums[i]] = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法一\n",
    "# 标签：数组遍历\n",
    "# 首先对数组进行排序，排序后固定一个数 nums[i]nums[i]nums[i]，再使用左右指针指向 nums[i]nums[i]nums[i]后面的两端，数字分别为 nums[L]nums[L]nums[L] 和 nums[R]nums[R]nums[R]，计算三个数的和 sumsumsum 判断是否满足为 000，满足则添加进结果集\n",
    "# 如果 nums[i]nums[i]nums[i]大于 000，则三数之和必然无法等于 000，结束循环\n",
    "# 如果 nums[i]nums[i]nums[i] == nums[i−1]nums[i-1]nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过\n",
    "# 当 sumsumsum == 000 时，nums[L]nums[L]nums[L] == nums[L+1]nums[L+1]nums[L+1] 则会导致结果重复，应该跳过，L++\n",
    "# 当 sumsumsum == 000 时，nums[R]nums[R]nums[R] == nums[R−1]nums[R-1]nums[R−1] 则会导致结果重复，应该跳过，R−−\n",
    "\n",
    "# class Solution:\n",
    "#     def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "#         if not nums or len(nums) < 3:\n",
    "#             return []\n",
    "        \n",
    "#         ans = []\n",
    "#         nums.sort()\n",
    "#         for i in range(0, len(nums)):\n",
    "#             if nums[i] > 0: # 因为排序过，所以第一个数》0了，sum三数之和肯定大于0了\n",
    "#                 break\n",
    "#             if i > 0 and nums[i] == nums[i-1]: # 去重第一个数\n",
    "#                 continue\n",
    "            \n",
    "#             # 左右指针从两边向中间对齐\n",
    "#             l = i + 1\n",
    "#             r = len(nums) - 1\n",
    "#             while l < r:\n",
    "#                 sum = nums[i] + nums[l] + nums[r]\n",
    "#                 left = nums[l]\n",
    "#                 right = nums[r]\n",
    "#                 if sum == 0:\n",
    "#                     ans.append([nums[i], nums[l], nums[r]])\n",
    "#                     # 去重第二、第三个数\n",
    "#                     while l < r and nums[l] == left:\n",
    "#                         l += 1\n",
    "#                     while l < r and nums[r] == right:\n",
    "#                         r -= 1\n",
    "#                     # l += 1\n",
    "#                     # r -= 1\n",
    "#                 elif sum < 0:\n",
    "#                     l += 1\n",
    "#                 elif sum > 0:\n",
    "#                     r -= 1\n",
    "#         return ans\n",
    "\n",
    "\n",
    "# 方法二：labuladong 排序+双指针\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        # n 为 3，从 nums[0] 开始计算和为 0 的三元组\n",
    "        # n 填写想求的是几数之和，start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和\n",
    "        ans = self.nSumTarget(nums, 3, 0, 0)\n",
    "\n",
    "        return ans\n",
    "    \n",
    "    def nSumTarget(self, nums, n, start, target):\n",
    "        if len(nums) < n:\n",
    "            return []\n",
    "        if n < 2:# 至少是2Sum\n",
    "            return []\n",
    "        \n",
    "        ans = []\n",
    "        l, r = start, len(nums) - 1\n",
    "        if n == 2: # 就是最好写的两数之和\n",
    "            while l < r:\n",
    "                sum_ = nums[l] + nums[r]\n",
    "                left, right = nums[l], nums[r]\n",
    "                if sum_ == target:\n",
    "                    ans.append([left, right])\n",
    "                    while l < r and nums[l] == left:\n",
    "                        l += 1\n",
    "                    while l < r and nums[r] == right:\n",
    "                        r -= 1\n",
    "                elif sum_ > target:\n",
    "                    while l < r and nums[r] == right:\n",
    "                        r -= 1\n",
    "                elif sum_ < target:\n",
    "                    while l < r and nums[l] == left:\n",
    "                        l += 1\n",
    "        else:\n",
    "            # 大于2Sum的，先求n-1\n",
    "            # n > 2 时，递归计算 (n-1)Sum 的结果，就想象成3Sum的，比较好理解\n",
    "            for i in range(start, len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i-1]: #去重\n",
    "                    continue\n",
    "\n",
    "                target_ = target - nums[i]\n",
    "                sub = self.nSumTarget(nums, n - 1, i + 1, target_)\n",
    "                for arr in sub:\n",
    "                    arr.append(nums[i])\n",
    "                    ans.append(arr)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法一\n",
    "# 标签：数组遍历\n",
    "# 首先对数组进行排序，排序后固定一个数 nums[i]nums[i]nums[i]，再使用左右指针指向 nums[i]nums[i]nums[i]后面的两端，数字分别为 nums[L]nums[L]nums[L] 和 nums[R]nums[R]nums[R]，计算三个数的和 sumsumsum 判断是否满足为 000，满足则添加进结果集\n",
    "# 如果 nums[i]nums[i]nums[i]大于 000，则三数之和必然无法等于 000，结束循环\n",
    "# 如果 nums[i]nums[i]nums[i] == nums[i−1]nums[i-1]nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过\n",
    "# 当 sumsumsum == 000 时，nums[L]nums[L]nums[L] == nums[L+1]nums[L+1]nums[L+1] 则会导致结果重复，应该跳过，L++\n",
    "# 当 sumsumsum == 000 时，nums[R]nums[R]nums[R] == nums[R−1]nums[R-1]nums[R−1] 则会导致结果重复，应该跳过，R−−\n",
    "\n",
    "# class Solution:\n",
    "#     def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "#         if not nums or len(nums) < 3:\n",
    "#             return []\n",
    "        \n",
    "#         ans = []\n",
    "#         nums.sort()\n",
    "#         for i in range(0, len(nums)):\n",
    "#             if nums[i] > 0: # 因为排序过，所以第一个数》0了，sum三数之和肯定大于0了\n",
    "#                 break\n",
    "#             if i > 0 and nums[i] == nums[i-1]: # 去重第一个数\n",
    "#                 continue\n",
    "            \n",
    "#             # 左右指针从两边向中间对齐\n",
    "#             l = i + 1\n",
    "#             r = len(nums) - 1\n",
    "#             while l < r:\n",
    "#                 sum = nums[i] + nums[l] + nums[r]\n",
    "#                 left = nums[l]\n",
    "#                 right = nums[r]\n",
    "#                 if sum == 0:\n",
    "#                     ans.append([nums[i], nums[l], nums[r]])\n",
    "#                     # 去重第二、第三个数\n",
    "#                     while l < r and nums[l] == left:\n",
    "#                         l += 1\n",
    "#                     while l < r and nums[r] == right:\n",
    "#                         r -= 1\n",
    "#                     # l += 1\n",
    "#                     # r -= 1\n",
    "#                 elif sum < 0:\n",
    "#                     l += 1\n",
    "#                 elif sum > 0:\n",
    "#                     r -= 1\n",
    "#         return ans\n",
    "\n",
    "\n",
    "# 方法二：labuladong 排序+双指针\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        # n 为 3，从 nums[0] 开始计算和为 0 的三元组\n",
    "        # n 填写想求的是几数之和，start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和\n",
    "        ans = self.nSumTarget(nums, 3, 0, 0)\n",
    "\n",
    "        return ans\n",
    "    \n",
    "    def nSumTarget(self, nums, n, start, target):\n",
    "        if len(nums) < n:\n",
    "            return []\n",
    "        if n < 2:# 至少是2Sum\n",
    "            return []\n",
    "        \n",
    "        ans = []\n",
    "        \n",
    "        if n == 2: # 就是最好写的两数之和\n",
    "        # 双指针那一套操作\n",
    "            l, r = start, len(nums) - 1\n",
    "            while l < r:\n",
    "                sum_ = nums[l] + nums[r]\n",
    "                left, right = nums[l], nums[r]\n",
    "                if sum_ == target:\n",
    "                    ans.append([left, right])\n",
    "                    while l < r and nums[l] == left:\n",
    "                        l += 1\n",
    "                    while l < r and nums[r] == right:\n",
    "                        r -= 1\n",
    "                elif sum_ > target:\n",
    "                    while l < r and nums[r] == right:\n",
    "                        r -= 1\n",
    "                elif sum_ < target:\n",
    "                    while l < r and nums[l] == left:\n",
    "                        l += 1\n",
    "        else:\n",
    "            # 大于2Sum的，先求n-1\n",
    "            # n > 2 时，递归计算 (n-1)Sum 的结果，就想象成3Sum的，比较好理解\n",
    "            for i in range(start, len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i-1]: #去重\n",
    "                    continue\n",
    "\n",
    "                target_ = target - nums[i]\n",
    "                sub = self.nSumTarget(nums, n - 1, i + 1, target_)\n",
    "                for arr in sub:\n",
    "                    # (n-1)Sum 加上 nums[i] 就是 nSum\n",
    "                    arr.append(nums[i])\n",
    "                    ans.append(arr) # 这里的ans是指最外层的ans，是[]。递归时候最里层的ans被用掉了，不为空。但代码跑到这时，用的是最外层的ans，为[]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        def find(l,r,target):\n",
    "            if l>r:\n",
    "                return r\n",
    "            now = (l+r) // 2\n",
    "            if nums[now] == target:\n",
    "                return now\n",
    "            if nums[now] < target:\n",
    "                return find(now+1,r,target)\n",
    "            if nums[now] > target:\n",
    "                return find(l,now-1,target)\n",
    "        res = []\n",
    "        i = 0\n",
    "        while(i<n-2):\n",
    "            if nums[i] + nums[i+1] + nums[i+2] > 0:\n",
    "                break\n",
    "            r = n-1\n",
    "            j = i+1\n",
    "            while(j<n-1):\n",
    "                target = 0-(nums[i]+nums[j])\n",
    "                l = j+1\n",
    "                if nums[l] > target:\n",
    "                    break\n",
    "                if nums[r] >= target and nums[l] <= target and l<=r:\n",
    "                    r = find(l,r,target)\n",
    "                    if nums[r] == target:\n",
    "                        res.append([nums[i],nums[j],nums[r]])\n",
    "                        r -= 1\n",
    "                j += 1\n",
    "                while(j<n and nums[j-1]==nums[j]):\n",
    "                    j += 1\n",
    "            i += 1\n",
    "            while(i<n and nums[i-1]==nums[i]):\n",
    "                i += 1\n",
    "        return res    \n",
    "        '''\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        nums.sort()\n",
    "        s = {}\n",
    "        pre_num = nums[0]\n",
    "        count = 1\n",
    "        for num in nums[1:]:\n",
    "            if pre_num == num:\n",
    "                count += 1\n",
    "            else:\n",
    "                s[pre_num] = count\n",
    "                pre_num = num\n",
    "                count = 1\n",
    "        s[pre_num] = count\n",
    "\n",
    "        res = []\n",
    "        i = 0\n",
    "        while(i<n-2):\n",
    "            if nums[i] + nums[i+1] + nums[i+2] > 0:\n",
    "                break\n",
    "            s[nums[i]] -= 1\n",
    "            s_tmp = s.copy()\n",
    "            j = i+1\n",
    "            while(j<n-1):\n",
    "                if nums[i] + nums[j] + nums[j+1] > 0:\n",
    "                    break \n",
    "                s_tmp[nums[j]] -= 1\n",
    "                target = (0-nums[i]-nums[j])\n",
    "                if s_tmp.get(target, 0) > 0:\n",
    "                    res.append([nums[i], nums[j], target])\n",
    "                s_tmp[nums[j]] = 0\n",
    "                j += 1\n",
    "                while(j<n and nums[j-1]==nums[j]):\n",
    "                    j += 1\n",
    "            s[nums[i]] = 0\n",
    "            i += 1\n",
    "            while(i<n and nums[i-1]==nums[i]):\n",
    "                i += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        def process(nums,tar):\n",
    "            i,j = 0,len(nums) - 1\n",
    "            result = []\n",
    "            hashmap = set()\n",
    "            while i < j:\n",
    "                if nums[i] in hashmap:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                if nums[j] in hashmap:\n",
    "                    j -= 1\n",
    "                    continue\n",
    "\n",
    "                cur = nums[i] + nums[j]\n",
    "                if cur > tar:\n",
    "                    j -= 1\n",
    "                elif cur < tar:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    if nums[i] not in hashmap or nums[j] not in hashmap:\n",
    "                        result.append([nums[i],nums[j],-1*tar])\n",
    "                        hashmap.add(nums[i])\n",
    "                        hashmap.add(nums[j])\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "            return result\n",
    "        \n",
    "        nums.sort()\n",
    "        result = []\n",
    "        hashmap = set()\n",
    "        while len(nums) > 2:\n",
    "            tar = nums.pop()\n",
    "            if tar in hashmap:\n",
    "                continue\n",
    "            hashmap.add(tar)\n",
    "            tp = process(nums,-1*tar)\n",
    "            if tp:\n",
    "                result.extend(tp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        str_set = set()\n",
    "        ans = []\n",
    "        for i in range(len(nums)-2):\n",
    "            num = nums[i]\n",
    "            num_dict = {}\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if -(nums[j] + nums[i]) in num_dict:\n",
    "                    seq = [nums[j], nums[i], -(nums[i]+nums[j])]\n",
    "                    seq.sort()\n",
    "                    if str(seq) not in str_set:\n",
    "                        ans.append(seq)\n",
    "                        str_set.add(str(seq))\n",
    "                num_dict[nums[j]] = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        nums_map = {value: index for index, value in enumerate(nums)}\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] > 0:\n",
    "                break\n",
    "            if i > 0 and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            for j in range(i + 1, n):\n",
    "                if j > i + 1 and nums[j] == nums[j - 1]:\n",
    "                    continue\n",
    "                val = - (nums[j] + nums[i])\n",
    "                if val in nums_map and nums_map[val] > j:\n",
    "                    ans.append([nums[i], nums[j], val])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        def find(l,r,target):\n",
    "            if l>r:\n",
    "                return r\n",
    "            now = (l+r) // 2\n",
    "            if nums[now] == target:\n",
    "                return now\n",
    "            if nums[now] < target:\n",
    "                return find(now+1,r,target)\n",
    "            if nums[now] > target:\n",
    "                return find(l,now-1,target)\n",
    "        res = []\n",
    "        i = 0\n",
    "        while(i<n-2):\n",
    "            r = n-1\n",
    "            j = i+1\n",
    "            while(j<n-1):\n",
    "                target = 0-(nums[i]+nums[j])\n",
    "                l = j+1\n",
    "                if nums[r] >= target and nums[l] <= target and l<=r:\n",
    "                    r = find(l,r,target)\n",
    "                    if nums[r] == target:\n",
    "                        res.append([nums[i],nums[j],nums[r]])\n",
    "                        r -= 1\n",
    "                j += 1\n",
    "                while(j<n and nums[j-1]==nums[j]):\n",
    "                    j += 1\n",
    "            i += 1\n",
    "            while(i<n and nums[i-1]==nums[i]):\n",
    "                i += 1\n",
    "        return res    \n",
    "        '''\n",
    "        n = len(nums)\n",
    "        s = {}\n",
    "        for num in nums:\n",
    "            if num in s.keys():\n",
    "                s[num] += 1\n",
    "            else:\n",
    "                s[num] = 1\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if s[nums[i]] == 0:\n",
    "                continue\n",
    "            s[nums[i]] -= 1\n",
    "            s_tmp = s.copy()\n",
    "            for j in range(i+1,n):\n",
    "                if s_tmp[nums[j]] == 0:\n",
    "                    continue\n",
    "                s_tmp[nums[j]] -= 1\n",
    "                target = (0-nums[i]-nums[j])\n",
    "                if s_tmp.get(target, 0) > 0:\n",
    "                    res.append([nums[i], nums[j], target])\n",
    "                s_tmp[nums[j]] = 0\n",
    "            s[nums[i]] = 0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        ans=set()\n",
    "        for i in range(len(nums)-2):\n",
    "            if nums[i]>0:break\n",
    "            for j in range(i+1,len(nums)-1):\n",
    "                num = nums[i]+nums[j]\n",
    "                m=j+1\n",
    "                n=len(nums)\n",
    "                while m<n:\n",
    "                    mid = ((n-m)>>1)+m\n",
    "                    if -num == nums[mid]:\n",
    "                        ans.add((nums[i],nums[j],nums[mid]))\n",
    "                        break\n",
    "                    if -num > nums[mid]:\n",
    "                        m=mid+1\n",
    "                    else:\n",
    "                        n=mid\n",
    "        return [list(i) for i in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, used, nums, ind, current, ans, h):\n",
    "        if len(current) == 2:\n",
    "            lacked = -sum(current)\n",
    "            if lacked in h:\n",
    "                ind_left = h[lacked]\n",
    "                if ind_left >= ind:\n",
    "                    current += [nums[ind_left]]\n",
    "                    ans.append(current)\n",
    "            return\n",
    "\n",
    "        current_sum = sum(current)\n",
    "        for i, num in enumerate(nums[ind:]):\n",
    "            if used[i+ind] == 1:\n",
    "                continue\n",
    "            elif i+ind > 0 and nums[i+ind-1] == num and used[i+ind-1] == 0: \n",
    "                continue\n",
    "            elif sum(nums[i+ind:i+ind+(3-len(current))]) + current_sum > 0:\n",
    "                break\n",
    "            elif sum(nums[len(current)-3:]) + current_sum < 0:\n",
    "                break\n",
    "            else:\n",
    "                used[i+ind] = 1\n",
    "                self.dfs(used, nums, i+ind+1, current+[num], ans, h)\n",
    "                used[i+ind] = 0\n",
    "        return\n",
    "\n",
    "    def twoSum(self, nums, target, ans):\n",
    "        si = 0\n",
    "        ei = len(nums)\n",
    "        while si < ei-1:\n",
    "            if nums[si] + nums[ei-1] < target:\n",
    "                si += 1\n",
    "            elif nums[si] + nums[ei-1] > target:\n",
    "                ei -= 1\n",
    "            else:\n",
    "                ans.append([-target, nums[si], nums[ei-1]])\n",
    "                si += 1\n",
    "                while si < ei and nums[si-1] == nums[si] :\n",
    "                    si += 1\n",
    "        return \n",
    "\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        for i, num in enumerate(nums[:-2]):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            if -num <= 2 * nums[-1] and -num >= 2 * nums[i+1]:\n",
    "                self.twoSum(nums[i+1:], -num, ans)\n",
    "        return ans\n",
    "        # nums.sort()\n",
    "        # si = 0\n",
    "        # ei = len(nums)-1\n",
    "        # # h = {n:i for i,n in enumerate(nums)}\n",
    "        # num2ind = {}\n",
    "        # ans = []\n",
    "        # for i, n in enumerate(nums):\n",
    "        #     if n not in num2ind:\n",
    "        #         num2ind[n] = i\n",
    "        \n",
    "        # while si + 1 < ei:\n",
    "        #     lacked = 0 - nums[ei] - nums[si]\n",
    "        #     if lacked in num2ind:\n",
    "        #         ans.append([nums[si], nums[num2ind[lacked]], nums[ei]])\n",
    "                \n",
    "        #     else:\n",
    "        #         if nums[si] + nums[ei-1] + nums[ei] < 0:\n",
    "        #             while nums[si] == nums[si+1] and si < ei:\n",
    "        #                 si += 1\n",
    "        #         elif nums[si] + nums[si+1] + nums[ei] > 0:\n",
    "        #             while nums[ei] == nums[ei-1] and si < ei:\n",
    "        #                 ei -= 1\n",
    "        #         else:\n",
    "        #             si += 1\n",
    "        # return ans\n",
    "\n",
    "\n",
    "    def threeSum1(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        h = {n:i for i,n in enumerate(nums)}\n",
    "        ans = []\n",
    "        current = []\n",
    "\n",
    "        used = [0] * len(nums)\n",
    "        self.dfs(used, nums, 0, current, ans, h)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)       \n",
    "        nums.sort()\n",
    "        # res = []\n",
    "        ans = set()\n",
    "        for i in range(n-2):\n",
    "            left = i + 1\n",
    "            right = n - 1\n",
    "            while left < right:\n",
    "                sum = nums[i] + nums[left] + nums[right]\n",
    "                    # res.append([nums[i],nums[left],nums[right]])\n",
    "                if sum < 0:\n",
    "                    left += 1\n",
    "                elif sum > 0:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    ans.add((nums[i],nums[left],nums[right]))\n",
    "                    left += 1\n",
    "                    right -= 1                    \n",
    "        return [list(a) for a in ans]\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self, used, nums, ind, current, ans, h):\n",
    "        if len(current) == 2:\n",
    "            # print(current)\n",
    "            lacked = -sum(current)\n",
    "            if lacked in h:\n",
    "                ind_left = h[lacked]\n",
    "                if ind_left >= ind:\n",
    "                    current += [nums[ind_left]]\n",
    "                    ans.append(current)\n",
    "            return\n",
    "\n",
    "        current_sum = sum(current)\n",
    "        for i, num in enumerate(nums[ind:]):\n",
    "            if used[i+ind] == 1:\n",
    "                continue\n",
    "            elif i+ind > 0 and nums[i+ind-1] == num and used[i+ind-1] == 0: \n",
    "                continue\n",
    "            elif sum(nums[i+ind:i+ind+(3-len(current))]) + current_sum > 0:\n",
    "                # print(\"to large\")\n",
    "                break\n",
    "            elif sum(nums[len(current)-3:]) + current_sum < 0:\n",
    "                # print(\"to small\")\n",
    "                break\n",
    "            else:\n",
    "                used[i+ind] = 1\n",
    "                self.dfs(used, nums, i+ind+1, current+[num], ans, h)\n",
    "                used[i+ind] = 0\n",
    "        return\n",
    "\n",
    "\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        # sorted(nums)\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        h = {n:i for i,n in enumerate(nums)}\n",
    "        ans = []\n",
    "        current = []\n",
    "\n",
    "        used = [0] * len(nums)\n",
    "        self.dfs(used, nums, 0, current, ans, h)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums=sorted(nums)\n",
    "        n=len(nums)\n",
    "        res=set()\n",
    "        for i in range(n-2):\n",
    "            k=n-1\n",
    "            for j in range(i+1,n-1):\n",
    "                while nums[i]+nums[j]+nums[k]>=0 and j<k:\n",
    "                    if nums[i]+nums[j]+nums[k]==0:\n",
    "                        res.add((nums[i],nums[j],nums[k]))\n",
    "                    k-=1\n",
    "                if j>=k:\n",
    "                    break\n",
    "        return [list(result) for result in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        ans = set()\n",
    "        n = len(nums)\n",
    "        for i in range(n - 2):\n",
    "            j = i + 1\n",
    "            k = n - 1\n",
    "            x = nums[i]\n",
    "            while j < k:\n",
    "                cur = x + nums[j] + nums[k]\n",
    "                if cur > 0:\n",
    "                    k -= 1\n",
    "                elif cur < 0:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    ans.add((x, nums[j], nums[k]))\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "        return [list(a) for a in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        #1e3 1e6<1e8\n",
    "\n",
    "        result=[]\n",
    "        r=set()\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            end=len(nums)-1\n",
    "            start=i+1\n",
    "            while start<end:\n",
    "                if nums[start]+nums[end]+nums[i]>0:\n",
    "                    end-=1\n",
    "                elif nums[start]+nums[end]+nums[i]<0:\n",
    "                    start+=1\n",
    "                elif nums[start]+nums[end]+nums[i]==0:\n",
    "                    if (nums[i],nums[start],nums[end]) not in r:\n",
    "                        result.append([nums[i],nums[start],nums[end]])\n",
    "                        r.add((nums[i],nums[start],nums[end]))\n",
    "                    start+=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums) < 3:\n",
    "            return []\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        start = 0\n",
    "        res_set = set()\n",
    "        for start in range(n - 2):\n",
    "            left = start + 1\n",
    "            right = n - 1\n",
    "            while left < right:\n",
    "                cur_sum = nums[start] + nums[left] + nums[right]\n",
    "                if cur_sum == 0:\n",
    "                    res_set.add((nums[start], nums[left], nums[right]))\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                elif cur_sum > 0:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "        res = [list(x) for x in res_set]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums):\n",
    "        # 排序\n",
    "        arr = sorted(nums)\n",
    "        res = []\n",
    "        nums_dict = dict()\n",
    "        # 遍历数组,\n",
    "        for i, num in enumerate(arr):\n",
    "            # 双指针判断是否存在两个数之和是 -num 的两个数存在\n",
    "            left, right = i + 1, len(arr) - 1\n",
    "            while left < right:\n",
    "                if arr[left] + arr[right] == -num:\n",
    "                    # 先判断是都在元组字典，不在添加res.更新元组\n",
    "                    if (num, arr[left], arr[right]) not in nums_dict:\n",
    "                        res.append([num, arr[left], arr[right]])\n",
    "                        nums_dict.update({(num, arr[left], arr[right]) :1})\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                elif arr[left] + arr[right] < -num:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        rs = set()\n",
    "        n = len(nums)\n",
    "        for idx,val in enumerate(nums):\n",
    "            if val == 0 and idx+2 < n and nums[idx+2] == 0:\n",
    "                rs.add((0,0,0))\n",
    "                continue\n",
    "            \n",
    "            target = -val\n",
    "            l,r = idx+1,n-1\n",
    "            while l < r:\n",
    "                s = nums[l]+nums[r]\n",
    "                if s == target:\n",
    "                    rs.add((val,nums[l],nums[r]))\n",
    "                    l += 1\n",
    "                elif s < target:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r -= 1 \n",
    "        return [[a,b,c] for (a,b,c) in rs]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums) < 3:\n",
    "            return []\n",
    "        \n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        firstnum_set = set()\n",
    "        ans_set = set()\n",
    "        for i in range(len(nums) - 2):\n",
    "            base = nums[i]\n",
    "            firstnum_set.add(base)\n",
    "            left = i + 1\n",
    "            right = len(nums) - 1\n",
    "            target = 0 - base\n",
    "\n",
    "            while left < right:\n",
    "                if nums[left] + nums[right] == target:\n",
    "                    if (base,nums[left],nums[right]) not in ans_set:\n",
    "                        ans.append([base,nums[left],nums[right]])\n",
    "                        ans_set.add((base,nums[left],nums[right]))\n",
    "                \n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                elif nums[left] + nums[right] < target:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums) < 3:\n",
    "            return []\n",
    "\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = set()\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] > 0:\n",
    "                break\n",
    "            j = i + 1\n",
    "            k = n - 1\n",
    "            while j < k:\n",
    "                tmp = nums[i] + nums[j] + nums[k]\n",
    "                if tmp == 0:\n",
    "                    ans.add((nums[i], nums[j], nums[k]))\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                elif tmp < 0:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    k -= 1\n",
    "\n",
    "        # ans = list(ans)\n",
    "\n",
    "        return [list(a) for a in ans]\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if i > 0 and nums[i] == nums[i-1]: continue\n",
    "            target = -num\n",
    "            dic = dict()\n",
    "            for j in range(i+1, len(nums)):\n",
    "                #if j > i+1 and nums[j] == nums[j-1]: continue\n",
    "                if target - nums[j] in dic:\n",
    "                    res.append([nums[i], nums[dic[target-nums[j]]], nums[j]])\n",
    "                else:\n",
    "                    dic[nums[j]] = j\n",
    "        res = list(sorted(l) for l in res)\n",
    "        res = list(set([tuple(t) for t in res]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        ans = set()\n",
    "        n = len(nums)\n",
    "        for i in range(n - 2):\n",
    "            j = i + 1\n",
    "            k = n - 1\n",
    "            x = nums[i]\n",
    "            while j < k:\n",
    "                cur = x + nums[j] + nums[k]\n",
    "                if cur > 0:\n",
    "                    k -= 1\n",
    "                elif cur < 0:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    ans.add((x, nums[j], nums[k]))\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "        return [list(a) for a in ans]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums):\n",
    "        reapt = []\n",
    "        self.tup = []\n",
    "        for i,x in enumerate(nums):\n",
    "            if x not in reapt:\n",
    "                reapt.append(x)\n",
    "                self.tup = self.tup + self.twosum(i,-x,nums)\n",
    "        return self.tup\n",
    "\n",
    "\n",
    "    def twosum(self, index, target, nums):\n",
    "        m = {}\n",
    "        tup1 = []\n",
    "        nums = nums[index+1:]\n",
    "        for i,x in enumerate(nums):\n",
    "            # nums1 = nums.copy()\n",
    "            # nums1.pop(i)\n",
    "            #nums1 = nums[i+1:] \n",
    "            if target-x in m:\n",
    "                temp = [-target, x,target-x]\n",
    "                temp.sort()\n",
    "                if temp not in tup1 and temp not in self.tup:\n",
    "                    tup1.append(temp)\n",
    "            m[x] = i\n",
    "        return tup1\n",
    "\n",
    "# class Solution:\n",
    "#     def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "#         n = len(nums)\n",
    "#         nums.sort()\n",
    "#         ans = list()\n",
    "        \n",
    "#         # 枚举 a\n",
    "#         for first in range(n):\n",
    "#             # 需要和上一次枚举的数不相同\n",
    "#             if first > 0 and nums[first] == nums[first - 1]:\n",
    "#                 continue\n",
    "#             # c 对应的指针初始指向数组的最右端\n",
    "#             third = n - 1\n",
    "#             target = -nums[first]\n",
    "#             # 枚举 b\n",
    "#             for second in range(first + 1, n):\n",
    "#                 # 需要和上一次枚举的数不相同\n",
    "#                 if second > first + 1 and nums[second] == nums[second - 1]:\n",
    "#                     continue\n",
    "#                 # 需要保证 b 的指针在 c 的指针的左侧\n",
    "#                 while second < third and nums[second] + nums[third] > target:\n",
    "#                     third -= 1\n",
    "#                 # 如果指针重合，随着 b 后续的增加\n",
    "#                 # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环\n",
    "#                 if second == third:\n",
    "#                     break\n",
    "#                 if nums[second] + nums[third] == target:\n",
    "#                     ans.append([nums[first], nums[second], nums[third]])\n",
    "        \n",
    "#         return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        tmp = {}\n",
    "        for i in range(len(nums)):\n",
    "            l = i-1\n",
    "            r = i+1\n",
    "            while l >= 0 and r < len(nums):\n",
    "                s = nums[l] + nums[i] + nums[r]\n",
    "                tmpl = nums[l]\n",
    "                tmpr = nums[r]\n",
    "                if s == 0:\n",
    "                    if str([nums[l], nums[i], nums[r]]) not in tmp:\n",
    "                        tmp[str([nums[l], nums[i], nums[r]])] = True\n",
    "                        res.append([nums[l], nums[i], nums[r]])\n",
    "                    r += 1\n",
    "                    l -= 1\n",
    "                elif s < 0:\n",
    "                    r += 1\n",
    "                else:\n",
    "                    l -= 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums):\n",
    "        reapt = []\n",
    "        self.tup = []\n",
    "        for i,x in enumerate(nums):\n",
    "            if x not in reapt:\n",
    "                reapt.append(x)\n",
    "                self.tup = self.tup + self.twosum(i,-x,nums)\n",
    "        return self.tup\n",
    "\n",
    "\n",
    "    def twosum(self, index, target, nums):\n",
    "        m = {}\n",
    "        tup1 = []\n",
    "        for i,x in enumerate(nums[index+1:]):\n",
    "            if target-x in m:\n",
    "                temp = [-target, x,target-x]\n",
    "                temp.sort()\n",
    "                if temp not in tup1 and temp not in self.tup:\n",
    "                    tup1.append(temp)\n",
    "            m[x] = i\n",
    "        return tup1\n",
    "\n",
    "# class Solution:\n",
    "#     def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "#         n = len(nums)\n",
    "#         nums.sort()\n",
    "#         ans = list()\n",
    "        \n",
    "#         # 枚举 a\n",
    "#         for first in range(n):\n",
    "#             # 需要和上一次枚举的数不相同\n",
    "#             if first > 0 and nums[first] == nums[first - 1]:\n",
    "#                 continue\n",
    "#             # c 对应的指针初始指向数组的最右端\n",
    "#             third = n - 1\n",
    "#             target = -nums[first]\n",
    "#             # 枚举 b\n",
    "#             for second in range(first + 1, n):\n",
    "#                 # 需要和上一次枚举的数不相同\n",
    "#                 if second > first + 1 and nums[second] == nums[second - 1]:\n",
    "#                     continue\n",
    "#                 # 需要保证 b 的指针在 c 的指针的左侧\n",
    "#                 while second < third and nums[second] + nums[third] > target:\n",
    "#                     third -= 1\n",
    "#                 # 如果指针重合，随着 b 后续的增加\n",
    "#                 # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环\n",
    "#                 if second == third:\n",
    "#                     break\n",
    "#                 if nums[second] + nums[third] == target:\n",
    "#                     ans.append([nums[first], nums[second], nums[third]])\n",
    "        \n",
    "#         return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 如果是已经排序好的话，则时间复杂度位 O(n^2)\n",
    "        def twosum(nums, start, target):\n",
    "            left, right = start, len(nums) - 1\n",
    "            lr_list = []\n",
    "            while left < right:\n",
    "                sumval = nums[left] + nums[right]\n",
    "                if sumval == target:\n",
    "                    lr_list.append([left, right])\n",
    "                    right -= 1\n",
    "                elif sumval > target:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "            return lr_list\n",
    "        nums.sort()\n",
    "        flagSet = set()\n",
    "        result = []\n",
    "        N = len(nums)\n",
    "        for i in range(N-2):\n",
    "            target = 0 - nums[i]\n",
    "            lr_list = twosum(nums, i+1, target)\n",
    "            if len(lr_list) != 0:\n",
    "                for lr in lr_list:\n",
    "                    lstr = str([nums[i], nums[lr[0]], nums[lr[1]]])\n",
    "                    if lstr not in flagSet:\n",
    "                        result.append([nums[i], nums[lr[0]], nums[lr[1]]])\n",
    "                        flagSet.add(lstr)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        result = set()\n",
    "        nums.sort()\n",
    "        for index, num in enumerate(nums):\n",
    "            start, end = index + 1, len(nums) - 1\n",
    "            target = -num\n",
    "            while start < end:\n",
    "                if nums[start] + nums[end] == target:\n",
    "                    result.add(tuple(sorted([nums[start], nums[end], num])))\n",
    "                    start += 1\n",
    "                    end -= 1\n",
    "                elif nums[start] + nums[end] < target:\n",
    "                    start += 1\n",
    "                else:\n",
    "                    end -= 1\n",
    "        result = [list(res) for res in result]\n",
    "        return list(result)\n",
    "\n",
    "\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
